The present invention relates to a high-level synthesis technique for an LSI circuit, for automatically synthesizing a hardwired logic digital circuit from a behavioral description.
Conventionally, a high-level synthesis technique has been known as a technique which is particularly effective for designing in a short time, for example, designing an ASIC (Application Specific Integrated Circuit).
High-level synthesis is a technique for automatically synthesizing a circuit from a behavioral description describing only algorithms for processing, without containing information relating to the structure of hardware. One example of documents which describe the details of conventional high-level synthesis techniques is xe2x80x9cHigh-Level Synthesisxe2x80x9d, Kluwer Academic Publishers.
The following description will briefly explain processes of automatically synthesizing a circuit from a behavioral description, using a conventional high-level synthesis technique.
[1. Conversion of Behavioral Description into CFG]
In high-level synthesis, first, a flow of control (control flow) of execution of a behavioral description is analyzed, and the behavioral description is converted into a model called a control flow graph (CFG) expressing the control flow of execution.
The CFG is a graph similar to a flow chart of a program. For example, the behavioral description shown in FIG. 23(a) is converted into the CFG shown in FIG. 23(b).
The CFG represents sequences (1), (2), (3), (4) of behavior containing no conditional branch in the behavioral description shown in FIG. 23(a) by partial behavioral nodes (5), (6), (7), (8) as shown in FIG. 23(b).
Moreover, the CFG represents a conditional statement (9) of the behavioral description shown in FIG. 23(a) by a branch node (10) and a merge node (11) as shown in FIG. 23(b), and the control flow of execution by control flow branches (12) through (19).
A conditional expression of the conditional statement (9) corresponds to the branch node (10). When the condition is satisfied, the control moves to an output (14) on the true side of the branch node (10). When the condition is not satisfied, the control moves to an output (15) on the false side of the branch node (10).
It is said that, when the condition is satisfied, a control flow branch connected to the output on the true side of the branch node becomes active. Similarly, it is said that, when the condition is not satisfied, a control flow branch connected to the output on the false side of the branch node becomes active.
In the CFG shown in FIG. 23(b), one of the outputs (14), (15) of the branch node (10), which is marked with a black circle, represents the output on the true side. Similarly, in other CFGs later described, an output marked with a black circle in each branch node is the output on the true side.
[2. Conversion of CFG into CDFG]
After the conversion of a behavioral description into a CFG is performed as described above, the data dependence (data flow) of the CFG is analyzed, and then the CFG is converted into a model called control data flow graph (CDFG) expressing the dependence in the execution sequence between operations.
For example, the CFG shown in FIG. 23(b) is converted into the CDFG shown in FIG. 24.
The CDFG is a graph expressing the data dependence and the control dependence by branches by representing operations (20) through (25) and a selector (26) as nodes. Here, the operations (20) through (24) are arithmetic operations, and the operation (25) is a conditional operation.
The operation (25) as a conditional operation outputs a control signal (27) representing whether a conditional decision is true or false. The selector (26) selects one of two inputs according to the value of the control signal (27), and outputs the selected input.
Since the multiplication of b=a*d at the partial behavioral node (5) in the CFG shown in FIG. 23(b) depends on the result of the operation of a=b*c, a branch representing data dependence is present between the operations (20) and (21) in the CDFG.
Since no data dependence exists between the operations (21) and (22), they can be executed parallel. On the other hand, since data dependence exists between the operations (20) and (21), they cannot be executed parallel.
The reason for converting a behavioral description into a CDFG in high-level synthesis is that the CDFG is a behavioral expression which not only ensures the behavior described by the behavioral description, but also allows generation of hardware that achieves parallel processing.
[3. Scheduling]
When the conversion of CFG into CDFG has been completed, scheduling is performed. Scheduling is a process of determining relative times at which input/output, operations, and selection by the selector in the CDFG are to be executed on a circuit.
FIG. 25 shows the result of scheduling the CDFG shown in FIG. 24. According to the result of scheduling, inputs b, c, e, f, output a, and operations (30), (31), (35) are executed in step s1, and input d, outputs b, d, g, operations (32), (33), (36), and selection (34) by the selector are executed in step s2.
[4. Allocation]
Allocation is a process of synthesizing a circuit by allocating arithmetic units to the operation nodes in the CDFG upon receipt of the result of scheduling, generating multiplexers for data selection, registers for data storage and a controller for controlling those and connecting them to each other.
FIG. 26 shows a circuit synthesized by the allocation according to the result of scheduling shown in FIG. 25.
[5. Behavioral Description Language for High-Level Synthesis]
For behavioral descriptions for high-level synthesis, procedure-oriented languages as well as many programming languages are usually used because the human""s thinking is consecutive and a behavior described by a procedure-oriented language is easily understood by the human. A typical example of procedure-oriented behavioral description languages is a VHDL language. Many of conventional synthesis tools adopt the VHDL language as the behavioral description language.
However, the VHDL language has not spread widely compared with usual programming languages. Therefore, when hardware is to be designed by an engineer who is unfamiliar with the VHDL language, he/she must learn the VHDL language, irrespective of whether he/she understands other programming languages.
Besides, hardware is designed by a method in which an algorithm is first verified by software and then hardware is realized by a behavioral description language. Namely, in such a method, rewriting from a programming language as a software description language to the VHDL language needs to be performed by an operator.
A typical example of the procedure-oriented programming languages is C language. The C language has been widely used as a language for describing software, and many engineers have already understood the C language. It is thus considered that the C language is suitably used as a behavioral description language for high-level synthesis.
If the C language is used as a behavioral description language for high-level synthesis, the C language used for verifying the algorithm by software can be used directly as an input for high-level synthesis. Hence, rewriting from the programming language into the VHDL language by the operator is not required.
A characteristic of the C language, which is not possessed by the VHDL language, is that the C language supports goto statements and switch statements for dispersing control of execution to another location in the description.
The goto statement is a command which instructs a jump to a description section labelled with the same label as a jump destination label given as an argument of the goto statement. The goto statement can be used as a jump command according to a condition by using it as a subordinate statement of an if statement.
The switch statement is a command for dispersing control of execution to description sections starting from each case according to the value of the conditional expression. If a break statement is executed in a subordinate sub-statement of the switch statement, the switch statement is completed.
When a plurality of execution paths include the same processing, the behavioral description can be shared by the plurality of execution paths by branching control of execution with the use of a goto statement or a switch statement. As a result, the behavior can be described simply.
In the VHDL language, there is a case statement having a function similar to the switch statement. However, the case statement in the VHDL language executes any one of specified processing statements according to the value of the conditional expression, and thus basically differs from the switch statement.
For instance, as shown in FIG. 12(a), with a conventional art, it is impossible to execute the break statement by a condition, or realize processing similar to processing containing no break statement in each case by the case statement in the VHDL language.
When a programming language such as the C language is adopted as a behavioral description language for high-level synthesis, it is necessary to support execution control branch instructions such as the switch statements and if-goto statements. A high-level synthesis system must generate a circuit for executing the behavior of the execution control branch instruction.
In the Neumann processor, the execution control branch instructions such as the switch statement and if-goto statement are executed using jump instructions of the processor. As in a stored program system like the Neumann processor in which instructions are sequentially read out from a memory and the behaviors of the instructions are executed, the jump instruction can be easily executed by inputting the address to which a jump is to be made in a program counter.
However, in a circuit generated by high-level synthesis, the behavioral description is not executed as software on the circuit of the stored program system, but is executed directly as the behavior of hardware on a hardwired circuit. In the hardwired circuit, no program counter exists. Therefore, in order to execute the execution control branch instructions such as the switch statement and if-goto statement, it is necessary to execute on the hardwired circuit the same behavior as that realized by the execution of these instructions.
In order to achieve this, it is necessary to express the behavior of the behavioral description including the execution control branch instructions by a CFG using branch nodes and merge nodes. If the behavior of the behavioral description including the execution control branch instructions is expressed by the CFG using branch nodes and merge nodes, it is possible to produce a hardwired circuit that executes the same behavior as that realized when the execution control branch instructions are executed by the Neumann processor according to the conventional CFG-to-CDFG conversion method, scheduling method, and allocation method. The CFG-to-CDFG conversion method, scheduling method of CDFG, and allocation method have been known in the field of high-level synthesis (see High-Level Synthesis, Kluwer Academic Publishers).
There is a possibility that a plurality of CFGs express the behavior of a single behavioral description. For example, both of the CFG shown in FIG. 3(b) and the CFG shown in FIG. 27 are a CFG expressing the behavior of the behavioral description shown in FIG. 3(a). When the CFG shown in FIG. 3(b) and the CFG shown in FIG. 27 are compared, the efficiency of the CFG shown in FIG. 27 is worse than the CFG shown in FIG. 3(b) because a partial behavior corresponding to the operation of b=a*2 is duplicated in the CFG shown in FIG. 27.
Both of the CFG shown in FIG. 12(b) and the CFG shown in FIG. 28 are a CFG expressing the behavior of the behavioral description shown in FIG. 12(a). When the CFG shown in FIG. 12(b) and the CFG shown in FIG. 28 are compared, the efficiency of the CFG shown in FIG. 28 is worse than the CFG shown in FIG. 12(b) because a partial behavior corresponding to the operation of f=(d+e)*6 is duplicated in the CFG shown in FIG. 28.
A circuit requiring high-speed processing employs a method in which both of a true path and a false path are executed at a branch of the CFG, and a necessary value is selected after a branch condition is determined.
For example, in the CFG shown in FIG. 23(b), only one of two behaviors represented by partial behavioral nodes (6), (7) is required depending on a condition corresponding to a branch node (10). However, according to the result of scheduling shown in FIG. 25 in which the processing is arranged to be completed by two steps, since a conditional decision by an operation (33) is made after performing operations (30), (31) corresponding to the behaviors (6), (7), it is necessary to execute both of the operations (30), (31) in advance.
In order to complete the processing by two steps, it is necessary to execute the operations (30), (31) in step s1, and therefore the operations (30), (31) cannot share a single arithmetic unit. Thus, in the circuit shown in FIG. 26 generated by the result of scheduling shown in FIG. 25, one adder and one subtracter exist for executing the operations (30), (31) concurrently.
On the other hand, if the conditional decision is made before the operations (30), (31) corresponding to the behaviors (6), (7), only one of the operations (30), (31) needs to be executed. In this case, hardware can be decreased by sharing an arithmetic unit. However, the processing cannot be completed by two steps.
As described above, with the use of the method in which both of the true path and false path are executed and then a necessary value is selected after deciding the branch condition, an arithmetic unit cannot be shared between the true path and the false path. Therefore, a partial behavior in the CFG is duplicated as described above, and an arithmetic unit cannot be shared between the duplicate partial behaviors. As a result, the area of the circuit is increased. It is thus necessary to minimize such duplication in generating a CFG.
Note that as a technique relating to the present invention, there is, for example, a program optimization method disclosed in Japanese patent publication of patent No. 2500079 (issued May 29, 1996). However, the method disclosed in this publication is a compiler technique for optimizing the execution performance of a software program including multi-way branch instructions, such as a statement, on condition that the instructions are executed by a stored program type Neumann processor, and is different from the present invention in at least a point that it is not a high-level synthesis technique performed on condition that the behavior of a behavioral description is executed on a hardwired circuit.
It is an object of the present invention to synthesize a hardwired circuit for executing the behaviors of execution control branch instructions such as if-goto statements and switch statements, rather than executing the behaviors on a stored program type Neumann processor as in the above-mentioned conventional techniques. It is another object of the present invention to generate a CFG without duplicate partial behaviors so as to generate an efficient circuit even when a method in which both of the true path and the false path are executed and a necessary value is selected after a branch condition is determined is adopted.
In order to achieve the above object, a hardware synthesis method according to the present invention is characterized in including the steps of:
(a) converting a behavioral description including an execution control branch instruction into a control flow graph;
(b) converting the control flow graph into a control data flow graph;
(c) performing scheduling according to the control data flow graph; and
(d) performing allocation according to the result of scheduling.
With this method, in step (a), a behavioral description including an execution control branch instruction can be expressed by a control flow graph using a branch node and a merge node. By executing steps (b) through (d) sequentially according to the control flow graph, it is possible to synthesize a hardwired circuit for executing the behavior of the execution control branch instruction by converting the control flow graph into a control data flow graph, and performing scheduling and allocation according to the control data flow graph. Namely, an execution control branch instruction such as an if-goto statement or a switch statement can be supported by a behavioral description language for high-level synthesis.
Moreover, a hardware synthesis device according to the present invention is characterized in including:
CFG generating means for converting a behavioral description containing an execution control branch instruction into a control flow graph;
CDFG generating means for converting the control flow graph into a control data flow graph;
scheduling means for performing scheduling according to the control data flow graph; and
allocation means for performing allocation according to the result of scheduling.
With this structure, the CFG generating means expresses a behavioral description including an execution control branch instruction by a control flow graph using a branch node and a merge node. According to the control flow graph, the CDFG generating means, scheduling means and allocation means convert the control flow graph into a control data flow graph, and performs scheduling and allocation in accordance with the control data flow graph. As a result, a hardwired circuit for executing the behavior of the execution control branch instruction is synthesized. Namely, a hardware synthesis device supporting execution control branch instructions can be realized by a behavioral description language for high-synthesis.
Furthermore, a recording medium containing a hardware synthesis program recorded thereon according to the present invention is characterized by the hardware synthesis program including the steps of:
(a) converting a behavioral description including an execution control branch instruction into a control flow graph;
(b) converting the control flow graph into a control data flow graph;
(c) performing scheduling according to the control data flow graph; and
(d) performing allocation according to the result of scheduling.
With this structure, it is possible to provide means for supporting a behavioral description including an execution control branch instruction by a behavioral description language for high-level synthesis.
For a fuller understanding of the nature and advantages of the invention, reference should be made to the ensuing detailed description taken in conjunction with the accompanying drawings.